(* local search with hill climbing *)

open Uav_data
open Target
open Planning


(* search large neighborhood *)
(* planning should be a copy of your local planning variable *)
let large_search = fun planning k p ->
  let select_n_tasks_from_planning = fun planning k ->
    (*let costs = cost_of_all_tasks planning.tasks planning.plans in*)
    let costs = Array.init n (fun _ -> Random.int 2000) in
    let ci = Array.mapi (fun i c -> (c,i)) costs in
      Array.sort (fun (c1,_) (c2,_) -> compare c1 c2) ci;
      Array.sub (Array.map (fun (_,x) -> x) ci) 0 n
  in
  let generate = fun planning ts ->
    for i=0 to Array.length ts -1 do
      let machines = available_machine_for_task ts.(i) planning.res in
      let machine  = select_from_list machines
      in 
      if ttype.(ts.(i)) = Dr 
      then planning.res.ball.(ts.(i)) <- planning.res.ball.(ts.(i)) -1;
      planning.tasks.(ts.(i)) <- machine;
      planning.plans.(machine) <- 
	Insertion.insert_at_best_position ts.(i) planning.plans.(machine) machine;
    done
  in
  let selection = select_n_tasks_from_planning planning k in
  let rec iter = fun l i ->
    if i=0 
    then l
    else begin      
      let new_planning = planning_copy planning in
	generate new_planning selection;
	iter (new_planning::l) (i-1)
    end
  in
    Array.iter (fun t -> remove_task_from_plan t planning) selection;
    iter [] p
    
let lns = fun () ->
  let t0 = Sys.time () in
  let res = {ball = Array.copy ball; video = Array.copy video } in
  let tasks = generate_random_alloc res in
  let plans = Insertion.generate_plans tasks in
  let planning = ref { tasks = tasks; res = res; plans = plans;} in
    while true do
      let pool = Array.of_list (large_search (planning_copy !planning ) (n/2) (50)) in
      let c = Array.map cost pool in
      let current_cost = Utils.min_array c in
      if cost !planning > current_cost then begin
	planning := pool.(Utils.arg_min c);
	Printf.printf "% 6.2f\t" (Sys.time () -. t0);
	print_solution !planning.tasks !planning.plans;
	trace !planning.plans
      end
    done
    

let iterative_greed = fun k ->
  let res = {ball = Array.copy ball; video = Array.copy video } in
  let tasks = generate_random_alloc res in
  let plans = Insertion.generate_plans tasks in
  let planning = ref { tasks = tasks; res = res; plans = plans;} in
    for i=1 to k-1 do
      let res = {ball = Array.copy ball; video = Array.copy video } in
      let tasks = generate_random_alloc res in
      let plans = Insertion.generate_plans tasks in
      let p = { tasks = tasks; res = res; plans = plans;} in
      if cost p < cost !planning then
	begin
	  planning := p;
	  print_solution !planning.tasks !planning.plans;
	  trace !planning.plans
	end
    done;
    !planning


let hc = fun () ->
  let remove_task_from_plan = fun t tasks plans res ->
    if ttype.(t) = Dr then res.ball.(tasks.(t)) <- res.ball.(tasks.(t)) +1;
    plans.(tasks.(t)) <- Array.of_list 
      (List.filter (fun x -> x<>t) (Array.to_list plans.(tasks.(t))));
    tasks.(t) <- -1;
  in
  let affect_task_to = fun t ac_id tasks plans res ->
    if ttype.(t) = Dr then res.ball.(ac_id) <- res.ball.(ac_id) -1;
    tasks.(t) <- ac_id;
    plans.(ac_id) <- Insertion.insert_at_best_position t plans.(ac_id) ac_id
  in
  (* Random.self_init (); *)
  let res = {ball = Array.copy ball; video = Array.copy video } in
  let tasks = generate_random_alloc res in
  let plans = Insertion.generate_plans tasks in
    print_solution tasks plans;
    let stop = ref false in
    while not !stop do
      let t = Utils.arg_max (cost_of_all_tasks tasks plans) in
      let old_machine = tasks.(t) in
	remove_task_from_plan t tasks plans res;
	
	let machines = available_machine_for_task t res in
	let c = Array.map 
	  (fun ac_id -> 
	     Insertion.insertion_cost_at_best_position t plans.(ac_id) ac_id
	  ) (Array.of_list machines) in
	let new_machine = List.nth machines (Utils.arg_min c) in
	  
	  affect_task_to t new_machine tasks plans res;
	  print_newline();
	  print_solution tasks plans;
	  if new_machine = old_machine then stop:= true;
    done


(* main of the program *)
let _ =
  lns ();
  Graphics.wait_next_event [Graphics.Key_pressed]

